


// 347. 前 K 个高频元素
// https://leetcode.cn/problems/top-k-frequent-elements/
// 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

 

// 示例 1:

// 输入: nums = [1,1,1,2,2,3], k = 2
// 输出: [1,2]

// 示例 2:

// 输入: nums = [1], k = 1
// 输出: [1]

 

// 提示：

//     1 <= nums.length <= 105
//     k 的取值范围是 [1, 数组中不相同的元素的个数]
//     题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

 

// 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。



class Solution {
    typedef pair<int, int> value_type;
    struct L
    {
        bool operator()(const value_type& x,const value_type& y) { return x.second < y.second; }
    };
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> m;
        vector<int> vk;
        priority_queue<value_type, vector<value_type>, L> pq;
        for(const auto& e : nums) ++m[e];

        // for(const auto& e : m)
        //     cout << e.first << " : " << e.second <<endl;
        for(const auto& e : m) pq.push(e);

        while(k--)
        {
            vk.push_back(pq.top().first);
            pq.pop();
        }

        return vk;
    }
};